<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="utf-8">
  <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport">
  
  <title itemprop="name">数据结构 | Yuki_Blog</title>
  
    <link rel="shortcut icon" href="/images/favicon.ico">
  
  <meta http-equiv="x-dns-prefetch-control" content="on">
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Noto+SerifMerriweather|Merriweather+Sans|Source+Code+Pro|Ubuntu:400,700|Noto+Serif+SC" media="all">
  <link rel="dns-prefetch" href="//cdn.jsdelivr.net">
  <link rel="stylesheet" id="saukra_css-css" href="/css/style.css" type="text/css" media="all">
  <link rel="stylesheet" href="/css/lib.min.css" media="all">
  <link rel="stylesheet" href="/css/font.css" media="all">
  <link rel="stylesheet" href="/css/insight.css" media="all">
  <link rel="stylesheet" href="/css/jquery.fancybox.min.css" media="all">
  <link rel="stylesheet" href="/css/zoom.css" media="all">
  <link rel="stylesheet" type="text/css" href="/css/sharejs.css">
<!--   <link rel="stylesheet" id="saukra_css-css" href="https://2heng.xin/wp-content/cache/autoptimize/css/autoptimize_ad42a61f4c7d4bdd9f91afcff6b5dda5.css
" type="text/css" media="all"> -->
  <script>
  /*Initial Variables*/
  var mashiro_option = new Object();
  var mashiro_global = new Object();
  mashiro_option.NProgressON = true;
  /* 
   * 邮箱信息之类的东西可以填在这里，这些js变量基本都作用于sakura-app.js
   * 这样的设置仅是为了方便在基于PHP开发的主题中设置js变量，既然移植到了Node上，我想或许可以精简这一逻辑吧
   */
  mashiro_option.email_domain = "";
  mashiro_option.email_name = "";
  mashiro_option.cookie_version_control = "";
  mashiro_option.qzone_autocomplete = false;
  mashiro_option.site_name = "YukiのBlog";
  mashiro_option.author_name = "Blog";
  mashiro_option.site_url = "https://kawaii-yuki.gitee.io";
  mashiro_option.v_appId = "kugxcpVLA8wXKraql2jEFO1r-gzGzoHsz";
  mashiro_option.v_appKey = "Le0otuGmt9RRFHunLbKL5Dj8";
  mashiro_option.mathjax = "0";
  mashiro_option.qq_api_url = "https://api.mashiro.top/qqinfo/"; 
  mashiro_option.qq_avatar_api_url = "https://api.mashiro.top/qqinfo/";

  // mashiro_option.jsdelivr_css_src = "https://cdn.jsdelivr.net/gh/moezx/cdn@3.4.5/css/lib.min.css";
  // mashiro_option.float_player_on = true;

  /*End of Initial Variables*/
  </script>
  <script type="text/javascript">
  var bg = "/images/cover/1.jpg".split(",");
  var bgindex = Math.floor(Math.random()*bg.length);
  if (!!window.ActiveXObject || "ActiveXObject" in window) { //is IE?
    alert('朋友，IE浏览器未适配哦~');
  }
  </script>
  <style type="text/css">
  .hljs-ln{border-collapse:collapse}.hljs-ln td{padding:0}.hljs-ln-n:before{content:attr(data-line-number)}
  </style>
  <style type="text/css">.site-top .lower nav{display:block !important;}.author-profile i,.post-like a,.post-share .show-share,.sub-text,.we-info a,span.sitename,.post-more i:hover,#pagination a:hover,.post-content a:hover,.float-content i:hover{color:#FE9600}.feature i,.download,.navigator i:hover,.links ul li:before,.ar-time i,span.ar-circle,.object,.comment .comment-reply-link,.siren-checkbox-radio:checked + .siren-checkbox-radioInput:after{background:#FE9600}::-webkit-scrollbar-thumb{background:#FE9600}.download,.navigator i:hover,.link-title,.links ul li:hover,#pagination a:hover,.comment-respond input[type='submit']:hover{border-color:#FE9600}.entry-content a:hover,.site-info a:hover,.comment h4 a,#comments-navi a.prev,#comments-navi a.next,.comment h4 a:hover,.site-top ul li a:hover,.entry-title a:hover,#archives-temp h3,span.page-numbers.current,.sorry li a:hover,.site-title a:hover,i.iconfont.js-toggle-search.iconsearch:hover,.comment-respond input[type='submit']:hover{color:#FE9600}.comments .comments-main{display:block !important;}.comments .comments-hidden{display:none !important;}background-position:center center;background-attachment:inherit;}
  </style>
<meta name="generator" content="Hexo 5.4.0"></head>

<script src="https://cdn.jsdelivr.net/gh/wallleap/cdn/js/sakura.js"></script>
<script src="https://cdn.jsdelivr.net/gh/wallleap/cdn/js/noSomeKey.js"></script>
<script src="https://cdn.jsdelivr.net/gh/wallleap/cdn/js/canvas-nest.min.js"></script>
<script src="https://cdn.jsdelivr.net/gh/stevenjoezhang/live2d-widget@latest/autoload.js"></script>
<body class="page-template page-template-user page-template-page-analytics page-template-userpage-analytics-php page page-id-1297 chinese-font serif isWebKit">
  <div class="scrollbar" id="bar">
  </div>
  <a href="#" class="cd-top faa-float animated"></a>
  <section id="main-container">
    <div class="headertop filter-dot">
  <div id="banner_wave_1"></div>
  <div id="banner_wave_2"></div>
  <figure id="centerbg" class="centerbg">
    <div class="focusinfo no-select">
      <div class="header-tou">
        <a target="_blank" rel="noopener" href="https://kawaii-yuki.gitee.io">
          <img src="/images/avatar.jpg">
        </a>
      </div>
      <div class="header-info">
        <p>有我有你 一鼓作气</p>
        <div class="top-social_v2">
          <li id="bg-pre">
            <img class="flipx" src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/next-b.svg">
          </li>
          
            
              
                <li>
                  <a href="https://github.com/sukixj" target="_blank" class="social-github" title="github">
                    <img src="/images/social/github.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://space.bilibili.com/42429348" target="_blank" class="social-github" title="bilibili">
                    <img src="/images/social/bilibili.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://weibo.com/u/2396685637" target="_blank" class="social-github" title="sina">
                    <img src="/images/social/sina.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://music.163.com/#/user/home?id=1754519629" target="_blank" class="social-github" title="wangyiyun">
                    <img src="/images/social/wangyiyun.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://www.zhihu.com/people/you-xi-sama-74" target="_blank" class="social-github" title="zhihu">
                    <img src="/images/social/zhihu.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="" target="_blank" class="social-github" title="email">
                    <img src="/images/social/email.svg">
                  </a>
                </li>
              
            
              
                <li class="wechat">
                  <a href="/#">
                    <img src="/images/social/wechat.png">
                  </a>
                  <div class="wechatInner">
                    <img src="/images/wechat.png">
                  </div>
                </li>
              
            
          
          <li id="bg-next">
            <img src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/next-b.svg">
          </li>
        </div>
      </div>
    </div>
  </figure>
  <div id="video-container" style="">
    <video style="object-fit: fill" id="bgvideo" class="video" video-name="" src="" width="auto" preload="auto">
    </video>
    <div id="video-btn" class="loadvideo videolive">
    </div>
    <div id="video-add">
    </div>
    <div class="video-stu">
    </div>
  </div>
  <div class="headertop-down faa-float animated" onclick="headertop_down()">
    <span>
      <i class="fa fa-chevron-down" aria-hidden="true">
      </i>
    </span>
  </div>
</div>
    <div id="page" class="site wrapper">
      <header class="site-header no-select gizle sabit" role="banner">
  <div class="site-top">
    <div class="site-branding">
      <span class="site-title">
        <span class="logolink moe-mashiro">
          <a href="/">
            <span class="sakurasono">Yukiの</span>
            <span class="shironeko">Blog</span>
          </a>
        </span>
      </span>
    </div>
    <div class="searchbox search-form-submit">
      <i class="iconfont js-toggle-search iconsearch icon-search">
      </i>
    </div>
    <div id="show-nav" class="showNav mobile-fit">
      <div class="line line1">
      </div>
      <div class="line line2">
      </div>
      <div class="line line3">
      </div>
    </div>
    <div class="lower-cantiner">
      <div class="lower">
        <nav class="mobile-fit-control hide">
          <ul id="menu-new" class="menu">
            
              <li>
                <a href="/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-fort-awesome faa-shake" aria-hidden="true"></i>
                    首页
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/archives">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-archive faa-shake" aria-hidden="true"></i>
                    归档
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/categories/%E6%8A%80%E6%9C%AF/">
                          <i class="fa fa-code" aria-hidden="true"></i>
                          技术
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E7%94%9F%E6%B4%BB/">
                          <i class="fa fa-file-text-o" aria-hidden="true"></i>
                          生活
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E8%B5%84%E6%BA%90/">
                          <i class="fa fa-cloud-download" aria-hidden="true"></i>
                          资源
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E9%9A%8F%E6%83%B3/">
                          <i class="fa fa-commenting-o" aria-hidden="true"></i>
                          随想
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E8%BD%AC%E8%BD%BD/">
                          <i class="fa fa-book" aria-hidden="true"></i>
                          转载
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="javascript:;">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-list-ul faa-vertical" aria-hidden="true"></i>
                    清单
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/tags/%E6%82%A6%E8%AF%BB/">
                          <i class="fa fa-th-list faa-bounce" aria-hidden="true"></i>
                          书单
                        </a>
                      </li>
                    
                      <li>
                        <a href="/bangumi/">
                          <i class="fa fa-film faa-vertical" aria-hidden="true"></i>
                          番组
                        </a>
                      </li>
                    
                      <li>
                        <a href="/music/">
                          <i class="fa fa-headphones" aria-hidden="true"></i>
                          歌单
                        </a>
                      </li>
                    
                      <li>
                        <a href="/tags/%E5%9B%BE%E9%9B%86/">
                          <i class="fa fa-photo" aria-hidden="true"></i>
                          图集
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="/comment/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-pencil-square-o faa-tada" aria-hidden="true"></i>
                    留言板
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/links/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-link faa-shake" aria-hidden="true"></i>
                    友人帐
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/donate/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-heart faa-pulse" aria-hidden="true"></i>
                    赞赏
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-leaf faa-wrench" aria-hidden="true"></i>
                    关于
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/about/">
                          <i class="fa fa-meetup" aria-hidden="true"></i>
                          我？
                        </a>
                      </li>
                    
                      <li>
                        <a href="/theme-sakura/">
                          <i class="fa iconfont icon-sakura" aria-hidden="true"></i>
                          主题
                        </a>
                      </li>
                    
                      <li>
                        <a href="/lab/">
                          <i class="fa fa-cogs" aria-hidden="true"></i>
                          Lab
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="/client/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-android faa-vertical" aria-hidden="true"></i>
                    客户端
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/atom.xml">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-rss faa-pulse" aria-hidden="true"></i>
                    RSS
                  </span>
                </a>
                
              </li>
            
          </ul>
        </nav>
      </div>
    </div>
  </div>
</header>

      <link rel="stylesheet" type="text/css" href="/css/sharejs.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/tocbot/4.4.2/tocbot.css">
<div class="pattern-center-blank"></div>

  <div class="pattern-center single-center">
    <!-- 有配图默认渲染第一张 -->
    <div class="pattern-attachment-img lazyload" style="background-image: url(https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg);" src="" data-src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg">
    </div>
    <header class="pattern-header single-header">
      <h1 class="entry-title">
      数据结构</h1>
      <p class="entry-census">
        <span>
          <a href="">
            <img src="">
          </a>
        </span>
        <span>
          <a href=""></a>
        </span>
        <span class="bull">
        ·</span>
        2017-10-20<span class="bull">
        ·</span>
      <span id="busuanzi_value_page_pv"></span>次阅读</p>
    </header>
  </div>

<div id="content" class="site-content">
  <div id="primary" class="content-area">
    <main id="main" class="site-main" role="main">
      <article id="post-1" class="post-1 post type-post status-publish format-standard has-post-thumbnail hentry category-uncategorized">
        <div class="toc"></div>
        <!--<div class="toc-entry-content"><!-- 套嵌目录使用（主要为了支援评论）-->
        
        <div class="entry-content">
          <h1 id="初级数据结构"><a href="#初级数据结构" class="headerlink" title="- 初级数据结构"></a>- 初级数据结构</h1><ul>
<li><h2 id="1、链表、双向链表"><a href="#1、链表、双向链表" class="headerlink" title="1、链表、双向链表"></a>1、链表、双向链表</h2></li>
<li><h4 id="定义链表："><a href="#定义链表：" class="headerlink" title="定义链表："></a>定义链表：</h4><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">LinkList</span> &#123;</span>  </span><br><span class="line">    <span class="keyword">int</span> value;  </span><br><span class="line">    LinkList *next;  </span><br><span class="line">&#125;;  </span><br></pre></td></tr></table></figure></li>
<li><h3 id="根据输入建立单链表"><a href="#根据输入建立单链表" class="headerlink" title="根据输入建立单链表"></a>根据输入建立单链表</h3></li>
</ul>
<p><strong>将输入的节点插入到链表头部。</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">LinkList *<span class="title">BuildList</span><span class="params">()</span> </span>&#123;  </span><br><span class="line">    LinkList *head = <span class="literal">NULL</span>;  </span><br><span class="line">    <span class="keyword">int</span> data;  </span><br><span class="line">    <span class="keyword">int</span> i = <span class="number">0</span>;  </span><br><span class="line">    <span class="keyword">while</span> (<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;data) != EOF) &#123;  </span><br><span class="line">        <span class="comment">//scanf(&quot;%d&quot;, &amp;data);++i;  </span></span><br><span class="line">        LinkList *new_node = (LinkList *)<span class="built_in">malloc</span>(<span class="built_in"><span class="keyword">sizeof</span></span>(LinkList));  </span><br><span class="line">        <span class="keyword">if</span> (<span class="literal">NULL</span> == new_node) &#123;  </span><br><span class="line">            <span class="built_in">fprintf</span>(stderr, <span class="string">&quot;malloc failed&quot;</span>);  </span><br><span class="line">            <span class="keyword">return</span> head;  </span><br><span class="line">        &#125;  </span><br><span class="line">        new_node-&gt;value = data;  </span><br><span class="line">        <span class="keyword">if</span> (head == <span class="literal">NULL</span>) &#123;  </span><br><span class="line">            new_node-&gt;next = <span class="literal">NULL</span>;  </span><br><span class="line">            head = new_node;  </span><br><span class="line">        &#125;  </span><br><span class="line">        <span class="keyword">else</span> &#123;  </span><br><span class="line">            new_node-&gt;next = head;  </span><br><span class="line">            head = new_node;  </span><br><span class="line">        &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> head;  </span><br><span class="line">&#125;  </span><br></pre></td></tr></table></figure>
<ul>
<li><h3 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//在链表头部插入节点  </span></span><br><span class="line"><span class="function">LinkList *<span class="title">InsertToHead</span><span class="params">(<span class="keyword">int</span> value, LinkList *head)</span> </span>&#123;  </span><br><span class="line">    LinkList *new_node = (LinkList *)<span class="built_in">malloc</span>(<span class="built_in"><span class="keyword">sizeof</span></span>(LinkList));  </span><br><span class="line">    <span class="keyword">if</span> (new_node == <span class="literal">NULL</span>) &#123;  </span><br><span class="line">        <span class="built_in">fprintf</span>(stderr, <span class="string">&quot;malloc failed&quot;</span>);  </span><br><span class="line">        <span class="keyword">return</span> head;  </span><br><span class="line">    &#125;  </span><br><span class="line">    new_node-&gt;value = value;  </span><br><span class="line">    new_node-&gt;next = <span class="literal">NULL</span>;  </span><br><span class="line">    <span class="keyword">if</span> (head == <span class="literal">NULL</span>) &#123;  </span><br><span class="line">        head = new_node;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">else</span> &#123;  </span><br><span class="line">        new_node-&gt;next = head;  </span><br><span class="line">        head = new_node;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> head;  </span><br><span class="line">&#125;  </span><br></pre></td></tr></table></figure>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//链表尾部插入节点</span></span><br><span class="line"><span class="function">LinkList *<span class="title">InsertToTail</span><span class="params">(<span class="keyword">int</span> value, LinkList *head)</span> </span>&#123;</span><br><span class="line">	LinkList *new_node = (LinkList *)<span class="built_in">malloc</span>(<span class="built_in"><span class="keyword">sizeof</span></span>(LinkList));</span><br><span class="line">	<span class="keyword">if</span> (new_node == <span class="literal">NULL</span>) &#123;</span><br><span class="line">		<span class="built_in">fprintf</span>(stderr, <span class="string">&quot;malloc failed&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> head;</span><br><span class="line">	&#125;</span><br><span class="line">	new_node-&gt;value = value;</span><br><span class="line">	new_node-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> (head == <span class="literal">NULL</span>)</span><br><span class="line">		head = new_node;</span><br><span class="line">	<span class="keyword">else</span> &#123;</span><br><span class="line">		LinkList *pnode = head;</span><br><span class="line">		<span class="keyword">while</span> (pnode-&gt;next != <span class="literal">NULL</span>)</span><br><span class="line">			pnode = pnode-&gt;next;</span><br><span class="line">		pnode-&gt;next = new_node;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></li>
<li><h3 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//删除某节点  </span></span><br><span class="line"><span class="function">LinkList *<span class="title">DeletebyValue</span><span class="params">(<span class="keyword">int</span> value, LinkList* head)</span> </span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> (head == <span class="literal">NULL</span>)  </span><br><span class="line">        <span class="keyword">return</span> head;  </span><br><span class="line">    LinkList *pToDelete = <span class="literal">NULL</span>;  </span><br><span class="line">    <span class="keyword">if</span> (head-&gt;value == value) &#123;  </span><br><span class="line">        pToDelete = head;  </span><br><span class="line">        head = head-&gt;next;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">else</span> &#123;  </span><br><span class="line">        LinkList *p = head;  </span><br><span class="line">        <span class="keyword">while</span> (p-&gt;next != <span class="literal">NULL</span> &amp;&amp; p-&gt;next-&gt;value != value)  </span><br><span class="line">            p = p-&gt;next;  </span><br><span class="line">        <span class="keyword">if</span> (p-&gt;next != <span class="literal">NULL</span>) &#123;  </span><br><span class="line">            pToDelete = p-&gt;next;  </span><br><span class="line">            p-&gt;next = pToDelete-&gt;next;  </span><br><span class="line">        &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">if</span> (pToDelete != <span class="literal">NULL</span>) &#123;  </span><br><span class="line">        <span class="built_in">free</span>(pToDelete);  </span><br><span class="line">        pToDelete = <span class="literal">NULL</span>;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> head;  </span><br><span class="line">&#125;  </span><br></pre></td></tr></table></figure></li>
<li><h3 id="求单链表中结点的个数"><a href="#求单链表中结点的个数" class="headerlink" title="求单链表中结点的个数"></a>求单链表中结点的个数</h3></li>
</ul>
<p><strong>注意检查链表是否为空。时间复杂度为O（n）。该操作不用特意检查链表是否为空，如下代码，链表为空会返回0。</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">unsigned</span> <span class="keyword">int</span> <span class="title">Length</span><span class="params">(LinkList *head)</span> </span>&#123;  </span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">int</span> length = <span class="number">0</span>;  </span><br><span class="line">    LinkList *p = head;  </span><br><span class="line">    <span class="keyword">while</span> (p) &#123;  </span><br><span class="line">        ++length;  </span><br><span class="line">        p = p-&gt;next;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> length;  </span><br><span class="line">&#125;  </span><br></pre></td></tr></table></figure>
<ul>
<li><h3 id="打印链表元素"><a href="#打印链表元素" class="headerlink" title="打印链表元素"></a>打印链表元素</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//打印单链表  顺序 </span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">PrintList</span><span class="params">(LinkList *head)</span> </span>&#123;  </span><br><span class="line">    LinkList *p = head;  </span><br><span class="line">    <span class="keyword">while</span> (p) &#123;  </span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, p-&gt;value);  </span><br><span class="line">        p = p-&gt;next;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);  </span><br><span class="line">&#125;  </span><br></pre></td></tr></table></figure></li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//逆序打印单链表：非递归  </span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">RPrintList</span><span class="params">(LinkList* head)</span> </span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> (<span class="literal">NULL</span> == head)  </span><br><span class="line">        <span class="keyword">return</span>;  </span><br><span class="line">    stack&lt;<span class="keyword">int</span>&gt; list_stack;  </span><br><span class="line">    <span class="keyword">while</span> (head) &#123;  </span><br><span class="line">        list_stack.<span class="built_in">push</span>(head-&gt;value);  </span><br><span class="line">        head = head-&gt;next;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">while</span> (!list_stack.<span class="built_in">empty</span>()) &#123;  </span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, list_stack.<span class="built_in">top</span>());  </span><br><span class="line">        list_stack.<span class="built_in">pop</span>();  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line"><span class="comment">//逆序打印单链表：递归  </span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">RPrintListRecursively</span><span class="params">(LinkList* head)</span> </span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> (<span class="literal">NULL</span> == head)  </span><br><span class="line">        <span class="keyword">return</span>;  </span><br><span class="line">    <span class="keyword">else</span> &#123;  </span><br><span class="line">        <span class="built_in">RPrintListRecursively</span>(head-&gt;next);  </span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, head-&gt;value);  </span><br><span class="line">    &#125;  </span><br><span class="line">&#125;  </span><br></pre></td></tr></table></figure>

<p><del><strong>双向链表是什么</strong></del></p>
<ul>
<li><h2 id="2、队列、单调队列、栈、单调栈"><a href="#2、队列、单调队列、栈、单调栈" class="headerlink" title="2、队列、单调队列、栈、单调栈"></a>2、队列、单调队列、栈、单调栈</h2></li>
<li><h3 id="队列："><a href="#队列：" class="headerlink" title="队列："></a>队列：</h3></li>
</ul>
<p><strong>遵循先进先出的原则（FIFO）的数据结构。</strong></p>
<ul>
<li><h4 id="STL："><a href="#STL：" class="headerlink" title="STL："></a>STL：</h4></li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;queue&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	queue &lt;<span class="keyword">int</span>&gt; qu;</span><br><span class="line">	<span class="keyword">int</span> a;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a);</span><br><span class="line">	qu.<span class="built_in">push</span>(a); <span class="comment">//插入元素 </span></span><br><span class="line">	<span class="keyword">if</span>(!qu.<span class="built_in">empty</span>()) &#123; <span class="comment">//判断队列是否为空 </span></span><br><span class="line">		cout&lt;&lt;qu.<span class="built_in">size</span>()&lt;&lt;endl; <span class="comment">//输出队列中元素个数 </span></span><br><span class="line">		cout&lt;&lt;qu.<span class="built_in">front</span>(); <span class="comment">//输出队首元素 </span></span><br><span class="line">		qu.<span class="built_in">pop</span>(); <span class="comment">//弹出队首元素 </span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li><h4 id="手写队列："><a href="#手写队列：" class="headerlink" title="手写队列："></a>手写队列：</h4></li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">queue</span> &#123;</span></span><br><span class="line">	<span class="keyword">int</span> Q[<span class="number">500005</span>],head,tail;</span><br><span class="line">	<span class="built_in">queue</span>() &#123;</span><br><span class="line">		head=<span class="number">0</span>,tail=<span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> a)</span> </span>&#123;</span><br><span class="line">		Q[++tail]=a;</span><br><span class="line">		<span class="keyword">return</span> ;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		head++;</span><br><span class="line">		<span class="keyword">return</span> ;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">empty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> head&gt;=tail;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">int</span> <span class="title">front</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> Q[head+<span class="number">1</span>];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">int</span> <span class="title">size</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span>(head&lt;=tail) <span class="keyword">return</span> tail-head; </span><br><span class="line">	&#125; </span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	queue qu;</span><br><span class="line">	<span class="keyword">int</span> a;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a);</span><br><span class="line">	qu.<span class="built_in">push</span>(a); <span class="comment">//插入元素 </span></span><br><span class="line">	<span class="keyword">if</span>(!qu.<span class="built_in">empty</span>()) &#123; <span class="comment">//判断队列是否为空 </span></span><br><span class="line">		cout&lt;&lt;qu.<span class="built_in">size</span>()&lt;&lt;endl; <span class="comment">//输出队列中元素个数 </span></span><br><span class="line">		cout&lt;&lt;qu.<span class="built_in">front</span>(); <span class="comment">//输出队首元素 </span></span><br><span class="line">		qu.<span class="built_in">pop</span>(); <span class="comment">//弹出队首元素 </span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li><h3 id="单调队列："><a href="#单调队列：" class="headerlink" title="单调队列："></a>单调队列：</h3></li>
</ul>
<p><strong>给定一个队列，维护三个操作。<br>1：将一个数x压入队列中。<br>2：求队列中数的最大值。<br>3：弹出队列尾的数。</strong></p>
<p><strong>这就要用到单调队列。</strong></p>
<p><strong>在每次进入队伍时，判断当前元素与队尾元素的大小关系，若小于队尾元素，则队尾不可能成为最小值，直接删除即可。<br>每次查询的答案一定在队首位置。<br>由于每个元素至多进队列和出队列一次，时间复杂度为O(n)。</strong></p>
<p><strong>下面以Sliding Window为例</strong></p>
<h4 id="STL（用deque（双端队列））"><a href="#STL（用deque（双端队列））" class="headerlink" title="STL（用deque（双端队列））"></a>STL（用deque（双端队列））</h4><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;deque&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> pair&lt;<span class="keyword">int</span>,<span class="keyword">int</span>&gt; P;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> maxn 1000000 + 10</span></span><br><span class="line"></span><br><span class="line">deque&lt;P&gt; Q1;</span><br><span class="line">deque&lt;P&gt; Q2;</span><br><span class="line"><span class="keyword">int</span> n,k;</span><br><span class="line"><span class="keyword">int</span> Min[maxn], Max[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(~<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;k)) &#123;</span><br><span class="line">		<span class="keyword">while</span>(!Q1.<span class="built_in">empty</span>()) Q1.<span class="built_in">pop_back</span>();</span><br><span class="line">		<span class="keyword">while</span>(!Q2.<span class="built_in">empty</span>()) Q2.<span class="built_in">pop_back</span>();</span><br><span class="line">		<span class="keyword">int</span> x;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>; i&lt;=n; i++) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;x);</span><br><span class="line">			<span class="keyword">while</span>(!Q1.<span class="built_in">empty</span>() &amp;&amp; Q1.<span class="built_in">back</span>().first &gt;= x) Q1.<span class="built_in">pop_back</span>();</span><br><span class="line">			Q1.<span class="built_in">push_back</span>(<span class="built_in">P</span>(x,i));</span><br><span class="line">			<span class="keyword">if</span>(i &gt;= k) &#123;</span><br><span class="line">				<span class="keyword">while</span>(!Q1.<span class="built_in">empty</span>() &amp;&amp; Q1.<span class="built_in">front</span>().second &lt;= i-k) Q1.<span class="built_in">pop_front</span>();</span><br><span class="line">				Min[i] = Q1.<span class="built_in">front</span>().first;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">while</span>(!Q2.<span class="built_in">empty</span>() &amp;&amp; Q2.<span class="built_in">back</span>().first &lt;= x) Q2.<span class="built_in">pop_back</span>();</span><br><span class="line">			Q2.<span class="built_in">push_back</span>(<span class="built_in">P</span>(x,i));</span><br><span class="line">			<span class="keyword">if</span>(i &gt;= k) &#123;</span><br><span class="line">				<span class="keyword">while</span>(!Q2.<span class="built_in">empty</span>() &amp;&amp; Q2.<span class="built_in">front</span>().second &lt;= i-k) Q2.<span class="built_in">pop_front</span>();</span><br><span class="line">				Max[i] = Q2.<span class="built_in">front</span>().first;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=k; i&lt;=n; i++)</span><br><span class="line">			i == n ? <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, Min[i]) : <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, Min[i]);</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=k; i&lt;=n; i++)</span><br><span class="line">			i == n ? <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, Max[i]) : <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, Max[i]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="手写"><a href="#手写" class="headerlink" title="手写"></a>手写</h4><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXN 1000005</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">s</span> &#123;</span></span><br><span class="line">	<span class="keyword">int</span> v,p;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">f</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span> </span>&#123;</span><br><span class="line">		v=a,p=b;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;Q1[MAXN],Q2[MAXN];</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> h1,t1,h2,t2,Min[MAXN],Max[MAXN];</span><br><span class="line"><span class="keyword">int</span> n,k;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;k);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) &#123;</span><br><span class="line">		<span class="keyword">int</span> x;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">		<span class="keyword">while</span>(h1&lt;t1 &amp;&amp; Q1[t1].v&gt;=x) t1--;</span><br><span class="line">		Q1[++t1].<span class="built_in">f</span>(x,i);</span><br><span class="line">		<span class="keyword">if</span>(i&gt;=k) &#123;</span><br><span class="line">			<span class="keyword">while</span>(h1&lt;t1 &amp;&amp; Q1[h1+<span class="number">1</span>].p&lt;=i-k) h1++;</span><br><span class="line">			Min[i]=Q1[h1+<span class="number">1</span>].v;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">while</span>(h2&lt;t2 &amp;&amp; Q2[t2].v&lt;=x) t2--;</span><br><span class="line">		Q2[++t2].<span class="built_in">f</span>(x,i);</span><br><span class="line">		<span class="keyword">if</span>(i&gt;=k) &#123;</span><br><span class="line">			<span class="keyword">while</span>(h2&lt;t2 &amp;&amp; Q2[h2+<span class="number">1</span>].p&lt;=i-k) h2++;</span><br><span class="line">			Max[i]=Q2[h2+<span class="number">1</span>].v;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=k;i&lt;=n;i++) <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>,Min[i]);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=k;i&lt;=n;i++) <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>,Max[i]);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<ul>
<li><h3 id="栈："><a href="#栈：" class="headerlink" title="栈："></a>栈：</h3></li>
</ul>
<p><strong>遵循先进后出的原则（FILO）的数据结构。</strong></p>
<ul>
<li><h4 id="STL"><a href="#STL" class="headerlink" title="STL:"></a>STL:</h4></li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stack&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    stack &lt;<span class="keyword">int</span>&gt; st;</span><br><span class="line">    <span class="keyword">int</span> a;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a);</span><br><span class="line">    st.<span class="built_in">push</span>(a); <span class="comment">//插入元素 </span></span><br><span class="line">    <span class="keyword">if</span>(!st.<span class="built_in">empty</span>()) &#123; <span class="comment">//判断栈是否为空 </span></span><br><span class="line">        cout&lt;&lt;st.<span class="built_in">size</span>()&lt;&lt;endl; <span class="comment">//输出栈中元素个数 </span></span><br><span class="line">        cout&lt;&lt;st.<span class="built_in">top</span>(); <span class="comment">//输出栈顶元素 </span></span><br><span class="line">        st.<span class="built_in">pop</span>(); <span class="comment">//弹出栈顶元素 </span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li><h4 id="手写："><a href="#手写：" class="headerlink" title="手写："></a>手写：</h4></li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">stack</span> &#123;</span></span><br><span class="line">	<span class="keyword">int</span> a[<span class="number">23333</span>],pos;</span><br><span class="line">	<span class="built_in">stack</span>() &#123;</span><br><span class="line">		pos=<span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">		a[++pos]=x;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		pos--;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">empty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> !pos;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">int</span> <span class="title">top</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> a[pos];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">int</span> <span class="title">size</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> pos;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    stack st;</span><br><span class="line">    <span class="keyword">int</span> a;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a);</span><br><span class="line">    st.<span class="built_in">push</span>(a); <span class="comment">//插入元素 </span></span><br><span class="line">    <span class="keyword">if</span>(!st.<span class="built_in">empty</span>()) &#123; <span class="comment">//判断栈是否为空 </span></span><br><span class="line">        cout&lt;&lt;st.<span class="built_in">size</span>()&lt;&lt;endl; <span class="comment">//输出栈中元素个数 </span></span><br><span class="line">        cout&lt;&lt;st.<span class="built_in">top</span>(); <span class="comment">//输出栈顶元素 </span></span><br><span class="line">        st.<span class="built_in">pop</span>(); <span class="comment">//弹出栈顶元素 </span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<ul>
<li><h3 id="单调栈"><a href="#单调栈" class="headerlink" title="单调栈"></a><del>单调栈</del></h3></li>
<li><h2 id="3、堆"><a href="#3、堆" class="headerlink" title="3、堆"></a>3、堆</h2><p><del><strong>STL多好用</strong></del></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;queue&gt;</span></span></span><br><span class="line">priority_queue &lt;<span class="keyword">int</span>&gt; big_heap; <span class="comment">//大根堆</span></span><br><span class="line">priority_queue &lt;<span class="keyword">int</span>,vector&lt;<span class="keyword">int</span>&gt;,greater&lt;<span class="keyword">int</span>&gt; &gt; small_heap; <span class="comment">//小根堆</span></span><br><span class="line">heap.<span class="built_in">top</span>();</span><br><span class="line">heap.<span class="built_in">push</span>();</span><br><span class="line">heap.<span class="built_in">pop</span>();</span><br><span class="line">heap.<span class="built_in">empty</span>();</span><br><span class="line">heap.<span class="built_in">size</span>();</span><br></pre></td></tr></table></figure></li>
</ul>
<p>手写：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">priority_queue</span> &#123;</span></span><br><span class="line">	<span class="keyword">int</span> a[<span class="number">23333</span>],size;</span><br><span class="line">	<span class="built_in">priority_queue</span>() &#123;</span><br><span class="line">		size=<span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">		a[++size]=x;</span><br><span class="line">		<span class="keyword">int</span> son=size,dad;</span><br><span class="line">		<span class="keyword">while</span>(son!=<span class="number">1</span>) &#123;</span><br><span class="line">			dad=son&gt;&gt;<span class="number">1</span>;</span><br><span class="line">			<span class="keyword">if</span>(a[dad]&gt;a[son]) <span class="built_in">swap</span>(a[dad],a[son]);</span><br><span class="line">			son=dad;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> ;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">int</span> <span class="title">top</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> a[<span class="number">1</span>];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		a[<span class="number">1</span>]=a[size--];</span><br><span class="line">		<span class="keyword">int</span> dad=<span class="number">1</span>,son=<span class="number">2</span>;</span><br><span class="line">		<span class="keyword">while</span>(son&lt;=size) &#123;</span><br><span class="line">			son=dad&lt;&lt;<span class="number">1</span>;</span><br><span class="line">			<span class="keyword">if</span>(son&lt;size &amp;&amp; a[son]&gt;a[son+<span class="number">1</span>]) son++;</span><br><span class="line">			<span class="keyword">if</span>(a[dad]&gt;a[son]) <span class="built_in">swap</span>(a[son],a[dad]);</span><br><span class="line">			dad=son;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> ;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">empty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> !size;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;; </span><br></pre></td></tr></table></figure>

<hr>
<h1 id="基础数据结构"><a href="#基础数据结构" class="headerlink" title="- 基础数据结构"></a>- 基础数据结构</h1><ul>
<li><h2 id="1、线段树"><a href="#1、线段树" class="headerlink" title="1、线段树"></a>1、线段树</h2></li>
</ul>
<p><strong>二分的思想把区间内的点分成若干个线段然后处理问题，查询和修改都是O（nlogn）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> lson l,m,rt&lt;&lt;1</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> rson m+1,r,rt&lt;&lt;1|1</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> maxn 1000005</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> ll <span class="title">read</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	ll x=<span class="number">0</span>,f=<span class="number">1</span>;<span class="keyword">char</span> ch=<span class="built_in">getchar</span>();</span><br><span class="line">	<span class="keyword">while</span>(ch&lt;<span class="string">&#x27;0&#x27;</span>||ch&gt;<span class="string">&#x27;9&#x27;</span>)&#123;<span class="keyword">if</span>(ch==<span class="string">&#x27;-&#x27;</span>)f=<span class="number">-1</span>;ch=<span class="built_in">getchar</span>();&#125;</span><br><span class="line">	<span class="keyword">while</span>(ch&gt;=<span class="string">&#x27;0&#x27;</span>&amp;&amp;ch&lt;=<span class="string">&#x27;9&#x27;</span>)&#123;x=x*<span class="number">10</span>+ch-<span class="string">&#x27;0&#x27;</span>;ch=<span class="built_in">getchar</span>();&#125;</span><br><span class="line">	<span class="keyword">return</span> x*f;</span><br><span class="line">&#125;</span><br><span class="line">ll a[maxn],sum[maxn&lt;&lt;<span class="number">2</span>],col[maxn&lt;&lt;<span class="number">2</span>];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">updata</span><span class="params">(ll rt)</span> </span>&#123;</span><br><span class="line">	sum[rt] = sum[rt&lt;&lt;<span class="number">1</span>] + sum[rt&lt;&lt;<span class="number">1</span>|<span class="number">1</span>];</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">color</span><span class="params">(ll l,ll r,ll rt,ll c)</span> </span>&#123;</span><br><span class="line">	col[rt]+=c;</span><br><span class="line">	sum[rt]+=c*(r-l+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">push_col</span><span class="params">(ll l,ll r,ll rt)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(col[rt]) &#123;</span><br><span class="line">		ll m=(l+r)&gt;&gt;<span class="number">1</span>;</span><br><span class="line">		<span class="built_in">color</span>(lson,col[rt]);</span><br><span class="line">		<span class="built_in">color</span>(rson,col[rt]);</span><br><span class="line">		col[rt]=<span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">build</span><span class="params">(ll l,ll r,ll rt)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(l==r) &#123;</span><br><span class="line">		sum[rt] = a[l];</span><br><span class="line">		<span class="keyword">return</span> ;</span><br><span class="line">	&#125;</span><br><span class="line">	ll m=(l+r)&gt;&gt;<span class="number">1</span>;</span><br><span class="line">	<span class="built_in">build</span>(lson);</span><br><span class="line">	<span class="built_in">build</span>(rson);</span><br><span class="line">	<span class="built_in">updata</span>(rt);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function">ll <span class="title">query</span><span class="params">(ll l,ll r,ll rt,ll L,ll R)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(L&lt;=l &amp;&amp; R&gt;=r)<span class="keyword">return</span> sum[rt];</span><br><span class="line">	<span class="built_in">push_col</span>(l,r,rt);</span><br><span class="line">	ll ret=<span class="number">0</span>;</span><br><span class="line">	ll m=(l+r)&gt;&gt;<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">if</span>(L&lt;=m) ret+=<span class="built_in">query</span>(lson,L,R);</span><br><span class="line">	<span class="keyword">if</span>(m&lt;R) ret+=<span class="built_in">query</span>(rson,L,R);</span><br><span class="line">	<span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">modify</span><span class="params">(ll l,ll r,ll rt,ll L,ll R,ll v)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(L&lt;=l &amp;&amp; R&gt;=r) &#123;</span><br><span class="line">		<span class="built_in">color</span>(l,r,rt,v);</span><br><span class="line">		<span class="keyword">return</span> ;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">push_col</span>(l,r,rt);</span><br><span class="line">	ll m=(l+r)&gt;&gt;<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">if</span>(L&lt;=m) <span class="built_in">modify</span>(lson,L,R,v);</span><br><span class="line">	<span class="keyword">if</span>(m&lt;R) <span class="built_in">modify</span>(rson,L,R,v);</span><br><span class="line">	<span class="built_in">updata</span>(rt);</span><br><span class="line">&#125;</span><br><span class="line">ll n,m;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	n=<span class="built_in">read</span>(),m=<span class="built_in">read</span>();</span><br><span class="line">	<span class="keyword">for</span>(ll i=<span class="number">1</span>;i&lt;=n;i++)a[i]=<span class="built_in">read</span>();</span><br><span class="line">	<span class="built_in">build</span>(<span class="number">1</span>,n,<span class="number">1</span>);</span><br><span class="line">	<span class="keyword">while</span>(m--) &#123;</span><br><span class="line">		ll id=<span class="built_in">read</span>();</span><br><span class="line">		<span class="keyword">if</span>(id==<span class="number">2</span>) &#123;</span><br><span class="line">			ll x=<span class="built_in">read</span>(),y=<span class="built_in">read</span>();</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%lld\n&quot;</span>,<span class="built_in">query</span>(<span class="number">1</span>,n,<span class="number">1</span>,x,y));</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			ll x=<span class="built_in">read</span>(),y=<span class="built_in">read</span>(),z=<span class="built_in">read</span>();</span><br><span class="line">			<span class="built_in">modify</span>(<span class="number">1</span>,n,<span class="number">1</span>,x,y,z);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<ul>
<li><h2 id="2、树状数组"><a href="#2、树状数组" class="headerlink" title="2、树状数组"></a>2、树状数组</h2></li>
</ul>
<p><strong>前缀和和差分的思想，利用二进制，反正就是跳来跳去。</strong><del><strong>反正背过就行。</strong></del><br><del><strong>就当存一下模板。</strong></del></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">1.将某一个数加上x</span></span><br><span class="line"><span class="comment">2.求出某区间每一个数的和</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXN 500005</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> a[MAXN],c[MAXN],n,m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lowbit</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">return</span> x&amp;(-x);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">modify</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(p&lt;=n) &#123;</span><br><span class="line">		c[p]+=x;</span><br><span class="line">		p+=<span class="built_in">lowbit</span>(p);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sum</span><span class="params">(<span class="keyword">int</span> p)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(p) &#123;</span><br><span class="line">		sum+=c[p];</span><br><span class="line">		p-=<span class="built_in">lowbit</span>(p);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">query</span><span class="params">(<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">return</span> <span class="built_in">sum</span>(r)-<span class="built_in">sum</span>(l<span class="number">-1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;m);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a[i]),<span class="built_in">modify</span>(i,a[i]);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++) &#123;</span><br><span class="line">		<span class="keyword">int</span> id,x,y;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>,&amp;id,&amp;x,&amp;y);</span><br><span class="line">		<span class="keyword">if</span>(id==<span class="number">1</span>) <span class="built_in">modify</span>(x,y); </span><br><span class="line">		<span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,<span class="built_in">query</span>(x,y));</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">1.将某区间每一个数数加上x</span></span><br><span class="line"><span class="comment">2.求出某一个数的和</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> maxn 500000+5</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n,m,pre,c[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lowbit</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">return</span> x&amp;(-x);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">modify</span><span class="params">(<span class="keyword">int</span> pos,<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(pos&lt;=n) &#123;</span><br><span class="line">		c[pos]+=x;</span><br><span class="line">		pos+=<span class="built_in">lowbit</span>(pos);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">query</span><span class="params">(<span class="keyword">int</span> pos)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(pos&gt;<span class="number">0</span>) &#123;</span><br><span class="line">		ans+=c[pos];</span><br><span class="line">		pos-=<span class="built_in">lowbit</span>(pos);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;m);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>; i&lt;=n; i++) &#123;</span><br><span class="line">		<span class="keyword">int</span> x;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">		<span class="built_in">modify</span>(i,x-pre);</span><br><span class="line">		pre=x;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span>(m--) &#123;</span><br><span class="line">		<span class="keyword">int</span> id;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;id);</span><br><span class="line">		<span class="keyword">if</span>(id==<span class="number">1</span>) &#123;</span><br><span class="line">			<span class="keyword">int</span> l,r,k;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>,&amp;l,&amp;r,&amp;k);</span><br><span class="line">			<span class="built_in">modify</span>(l,k);</span><br><span class="line">			<span class="built_in">modify</span>(r+<span class="number">1</span>,-k);</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">int</span> pos;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;pos);</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,<span class="built_in">query</span>(pos));</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li><h2 id="ST表"><a href="#ST表" class="headerlink" title="ST表"></a>ST表</h2></li>
</ul>
<p><strong>给定一个数列a，O(nlogn)预处理，O(1)查询数列在区间[l,r]的最值。<br>这里介绍求最大值。</strong><br><img src="https://img-blog.csdnimg.cn/img_convert/0ab1423701940ee6596ece231c31fbc3.png"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> st[N][K],a[N],log_2[N];</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">ini_st</span><span class="params">()</span></span>&#123;</span><br><span class="line">    log_2[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">2</span>;i&lt;=n;++i)&#123;</span><br><span class="line">        log_2[i]=log_2[i<span class="number">-1</span>];</span><br><span class="line">        <span class="keyword">if</span>((<span class="number">1</span>&lt;&lt;log_2[i]+<span class="number">1</span>)==i)</span><br><span class="line">            ++log_2[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=n;i;--i)&#123;</span><br><span class="line">        st[i][<span class="number">0</span>]=a[i];</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;(i+(<span class="number">1</span>&lt;&lt;j)<span class="number">-1</span>)&lt;=n;++j)</span><br><span class="line">            st[i][j]=<span class="built_in">max</span>(st[i][j<span class="number">-1</span>],st[i+(<span class="number">1</span>&lt;&lt;j<span class="number">-1</span>)][j<span class="number">-1</span>]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> <span class="title">ask</span><span class="params">(<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> k=log_2[r-l+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">max</span>(st[l][k],st[r-(<span class="number">1</span>&lt;&lt;k)+<span class="number">1</span>][k]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<ul>
<li><h2 id="并查集"><a href="#并查集" class="headerlink" title="并查集"></a>并查集</h2>貌似我在图伦里写过了。</li>
<li><h3 id="带权并查集"><a href="#带权并查集" class="headerlink" title="带权并查集"></a><del>带权并查集</del></h3></li>
<li><hr>
</li>
<li><h2 id="hash表"><a href="#hash表" class="headerlink" title="hash表"></a>hash表</h2></li>
</ul>
<p><strong>这个主要用于字符串hash，整理字符串的时候在写吧。</strong></p>
<hr>
<ul>
<li><h2 id="分块"><a href="#分块" class="headerlink" title="分块"></a>分块</h2></li>
</ul>
<p><strong>把问题分成许多（一般是根号n）块，在块中完成。时间复杂度为O（m根号n）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> belong[maxn],block,num,l[<span class="number">1000</span>],r[<span class="number">1000</span>];</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n,m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">build</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	block=<span class="built_in">sqrt</span>(n);</span><br><span class="line">	num=block;</span><br><span class="line">	<span class="keyword">if</span>(n%num)num++;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++) &#123;</span><br><span class="line">		belong[i]=(i<span class="number">-1</span>)/block;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=num;i++) &#123;</span><br><span class="line">		l[i]=(i<span class="number">-1</span>)*block;</span><br><span class="line">		r[i]=i*block<span class="number">-1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	r[num]=n;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<hr>

        </div>
        <!-- .entry-content -->
        <div class="single-reward">
          <div class="reward-open">赏
            <div class="reward-main">
              <ul class="reward-row">
                <li class="alipay-code"><img src="/images/donate/AliPayQR.jpg"></li>
                <li class="wechat-code"><img src="/images/donate/WeChanQR.jpg"></li>
              </ul>
            </div>
          </div>
        </div>
        <div style="text-align:center; width: 100%" class="social-share share-mobile" data-disabled="diandian, tencent"></div>
        <footer class="post-footer">
          <div class="post-lincenses"><a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" target="_blank" rel="nofollow"><i class="fa fa-creative-commons" aria-hidden="true"></i> 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议</a></div>
          <div class="post-tags">
          </div>
          <div class="post-share">
            <div class="social-share sharehidden share-component"></div>
            <i class="iconfont show-share icon-forward"></i>
          </div>
        </footer><!-- .entry-footer -->
      </article>
      <!-- #post-## -->
      <div class="toc" style="background: none;"></div>
      <section class="post-squares nextprev">
        
          
            <div class="post-nepre half previous">
          
            <a href="/2017/10/21/string/" rel="prev">
              <div class="background">
                <img class="lazyload" src="" data-src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg" style="width: 100%; height: 100%; object-fit: cover; pointer-events: none;" onerror="imgError(this,3)" src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg">
              </div>
              <span class="label">
              Previous Post</span>
              <div class="info">
                <h3>
                字符串</h3>
                <hr>
              </div>
            </a>
          </div>
        
        
          
            <div class="post-nepre half next">
          
            <a href="/2017/10/19/graph/" rel="next">
              <div class="background">
                <img class="lazyload" src="" data-src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg" style="width: 100%; height: 100%; object-fit: cover; pointer-events: none;" onerror="imgError(this,3)" src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg">
              </div>
              <span class="label">
              Next Post</span>
              <div class="info">
                <h3>
                图论</h3>
                <hr>
              </div>
            </a>
          </div>
        
      </section>
      
<div id="vcomments"></div>
<script>
  window.onload = function(){
      var valine = new Valine();
      valine.init({
        el: '#vcomments',
        appId: "kugxcpVLA8wXKraql2jEFO1r-gzGzoHsz",
        appKey: "Le0otuGmt9RRFHunLbKL5Dj8",
        path: window.location.pathname,
        placeholder: "你是我一生只会遇见一次的惊喜 ..."
      })
  }
</script>

      <section class="author-profile">
        <div class="info" itemprop="author" itemscope="" itemtype="https://schema.org/Person">
          <a href="" class="profile gravatar"><img src="" itemprop="image" alt="" height="70" width="70"></a>
          <div class="meta">
            <span class="title">Author</span>
            <h3 itemprop="name">
            <a href="" itemprop="url" rel="author"></a>
            </h3>
          </div>
        </div>
        <hr>
        <p><i class="iconfont icon-write"></i></p>
      </section>
    </main><!-- #main -->
  </div><!-- #primary -->
</div>



    </div>    
    <div class="ins-search">
    <div class="ins-search-mask"></div>
    <div class="ins-search-container">
        <div class="ins-input-wrapper">
            <input type="text" class="ins-search-input" placeholder="请输入关键词..."/>
            <span class="ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: '文章',
            // PAGES: '页面',
            CATEGORIES: '分类',
            TAGS: '标签',
        },
        ROOT_URL: '/',
        CONTENT_URL: '/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>
    <!-- <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2021 Yuki<br>
      powered_by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer> -->
<footer id="colophon" class="site-footer" role="contentinfo">
  <div class="site-info">
    <div class="footertext">
      <div class="img-preload">
        <img src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/wordpress-rotating-ball-o.svg">
        <img src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/disqus-preloader.svg">
      </div>
      <p style="color: #666666;">&copy 2018</p>
    </div>
    <div class="footer-device">
    <p style="font-family: 'Ubuntu', sans-serif;">
        <span style="color: #b9b9b9;">Theme <a href="https://github.com/honjun/hexo-theme-sakura" target="_blank" style="color: #b9b9b9;;text-decoration: underline dotted rgba(0, 0, 0, .1);">Sakura</a> <i class="iconfont icon-sakura rotating" style="color: #ffc0cb;display:inline-block"></i> by <a href="https://2heng.xin/" target="_blank" style="color: #b9b9b9;;text-decoration: underline dotted rgba(0, 0, 0, .1);">Mashiro</a>&<a href="https://www.hojun.cn/" target="_blank" style="color: #b9b9b9;;text-decoration: underline dotted rgba(0, 0, 0, .1);">Hojun</a>, Powered by Hexo, Hosted by Coding Pages</a>
        </span>
      </p>
    </div>
  </div><!-- .site-info -->
</footer>



<!-- <script src="/js/tocbot.js"></script> -->
<script type="text/javascript" src="/js/lib.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script type="text/javascript" src="/js/InsightSearch.js"></script>
<script type="text/javascript" src="/js/jquery.fancybox.min.js"></script>
<script type="text/javascript" src="/js/zoom.min.js"></script>
<script type="text/javascript" src="/js/sakura-app.js"></script>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src='//unpkg.com/valine@1.3.4/dist/Valine.min.js'></script>
<script src="/js/botui.js"></script>
<!-- 不蒜子 网页计数器 -->
<script src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<!-- <script src="https://cdnjs.cloudflare.com/ajax/libs/tocbot/4.4.2/tocbot.min.js"></script> -->
<script type="text/javascript">
/* <![CDATA[ */
if (/Android|webOS|iPhone|iPod|BlackBerry/i.test(navigator.userAgent)) {
  var Poi = {"pjax":"1","movies":{"url": "","name":"Unbroken.mp4","live":"close"},"windowheight":"fixed","codelamp":"close","ajaxurl":"","order":"asc","formpostion":"bottom"};
} else {
  var Poi = {"pjax":"1","movies":{"url": "","name":"Unbroken.mp4","live":"open"},"windowheight":"auto","codelamp":"close","ajaxurl":"","order":"asc","formpostion":"bottom"};
}
/* ]]> */

</script>
<script>
$(document).ready(function() {
  if ($(".toc").length > 0 && document.body.clientWidth > 1200) {
    if ($(".pattern-center").length > 0) { //有图的情况
      tocbot.init({
          // Where to render the table of contents.
          tocSelector: '.toc', // 放置目录的容器
          // Where to grab the headings to build the table of contents.
          contentSelector: '.entry-content', // 正文内容所在
          // Which headings to grab inside of the contentSelector element.
          scrollSmooth: true,
          headingSelector: 'h1, h2, h3, h4, h5', // 需要索引的标题级别
          headingsOffset: -400,
          scrollSmoothOffset: -85
      });
    } else {
      tocbot.init({
          // Where to render the table of contents.
          tocSelector: '.toc', // 放置目录的容器
          // Where to grab the headings to build the table of contents.
          contentSelector: '.entry-content', // 正文内容所在
          // Which headings to grab inside of the contentSelector element.
          scrollSmooth: true,
          headingSelector: 'h1, h2, h3, h4, h5', // 需要索引的标题级别
          headingsOffset: -85,
          scrollSmoothOffset: -85
      });
    }
    var offsetTop = $('.toc').offset().top - 95;
    window.onscroll = function() {
      var scrollTop = window.pageYOffset || document.documentElement.scrollTop || document.body.scrollTop;
      if (scrollTop >= offsetTop) {
        $('.toc').addClass('toc-fixed');
      } else {
        $('.toc').removeClass('toc-fixed');
      }
    }
  }
});
</script>

    <div class="openNav no-select" style="height: 50px;">
      <div class="iconflat no-select" style="width: 50px; height: 50px;">
        <div class="icon"></div>
      </div>
      <div class="site-branding search-form-submit">
        <i class="iconfont js-toggle-search iconsearch icon-search"></i>
      </div>
    </div>
  </section>
  <div id="mo-nav" class="">
  <div class="m-avatar">
    <img src="/images/avatar.jpg">
  </div>
  <p style="text-align: center; color: #333; font-weight: 900; font-family: 'Ubuntu', sans-serif; letter-spacing: 1.5px">YukiのBlog</p>
  <p style="text-align: center; word-spacing: 20px;">
    
      
        <a href="https://github.com/sukixj" class="fa fa-github" target="_blank" style="color: #333; margin-left:20px"></a>
      
        <a href="https://weibo.com/u/2396685637" class="fa fa-weibo" target="_blank" style="color: #dd4b39; margin-left:20px"></a>
      
        <a href="https://qm.qq.com/cgi-bin/qm/qr?k=uytBaS8dNXwkPgV_ZxWO_kTG5fruS0va&noverify=0" class="fa fa-qq" target="_blank" style="color: #25c6fe; margin-left:20px"></a>
      
    
  </p>
  <ul id="menu-new-1" class="menu">
    
      <li>
        <a href="/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-fort-awesome faa-shake" aria-hidden="true"></i>
            首页
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/archives">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-archive faa-shake" aria-hidden="true"></i>
            归档
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/categories/%E6%8A%80%E6%9C%AF/">
                  <i class="fa fa-code" aria-hidden="true"></i>
                  技术
                </a>
              </li>
            
              <li>
                <a href="/categories/%E7%94%9F%E6%B4%BB/">
                  <i class="fa fa-file-text-o" aria-hidden="true"></i>
                  生活
                </a>
              </li>
            
              <li>
                <a href="/categories/%E8%B5%84%E6%BA%90/">
                  <i class="fa fa-cloud-download" aria-hidden="true"></i>
                  资源
                </a>
              </li>
            
              <li>
                <a href="/categories/%E9%9A%8F%E6%83%B3/">
                  <i class="fa fa-commenting-o" aria-hidden="true"></i>
                  随想
                </a>
              </li>
            
              <li>
                <a href="/categories/%E8%BD%AC%E8%BD%BD/">
                  <i class="fa fa-book" aria-hidden="true"></i>
                  转载
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-list-ul faa-vertical" aria-hidden="true"></i>
            清单
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/tags/%E6%82%A6%E8%AF%BB/">
                  <i class="fa fa-th-list faa-bounce" aria-hidden="true"></i>
                  书单
                </a>
              </li>
            
              <li>
                <a href="/bangumi/">
                  <i class="fa fa-film faa-vertical" aria-hidden="true"></i>
                  番组
                </a>
              </li>
            
              <li>
                <a href="/music/">
                  <i class="fa fa-headphones" aria-hidden="true"></i>
                  歌单
                </a>
              </li>
            
              <li>
                <a href="/tags/%E5%9B%BE%E9%9B%86/">
                  <i class="fa fa-photo" aria-hidden="true"></i>
                  图集
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/comment/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-pencil-square-o faa-tada" aria-hidden="true"></i>
            留言板
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/links/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-link faa-shake" aria-hidden="true"></i>
            友人帐
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/donate/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-heart faa-pulse" aria-hidden="true"></i>
            赞赏
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-leaf faa-wrench" aria-hidden="true"></i>
            关于
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/about/">
                  <i class="fa fa-meetup" aria-hidden="true"></i>
                  我？
                </a>
              </li>
            
              <li>
                <a href="/theme-sakura/">
                  <i class="fa iconfont icon-sakura" aria-hidden="true"></i>
                  主题
                </a>
              </li>
            
              <li>
                <a href="/lab/">
                  <i class="fa fa-cogs" aria-hidden="true"></i>
                  Lab
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/client/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-android faa-vertical" aria-hidden="true"></i>
            客户端
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/atom.xml">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-rss faa-pulse" aria-hidden="true"></i>
            RSS
          </span>
        </a>
        
      </li>
    
  </ul>
  <p style="text-align: center; font-size: 13px; color: #b9b9b9;">&copy 2019 hexo-sakura</p>
</div>
<button onclick="topFunction()" class="mobile-cd-top" id="moblieGoTop" title="Go to top" style="display: none;"><i class="fa fa-chevron-up" aria-hidden="true"></i></button>
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css">
<script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script>
<!-- require MetingJS -->
<script src="https://cdn.jsdelivr.net/npm/meting@2/dist/Meting.min.js"></script>
<style>
  .aplayer .aplayer-lrc {
    height: 35px;
  }
  .aplayer .aplayer-lrc p{
    font-size: 16px;
    font-weight: 700;
    line-height: 18px !important;
  }
  .aplayer .aplayer-lrc p.aplayer-lrc-current{
    color: #FF1493;
  }
  .aplayer.aplayer-narrow .aplayer-body{
    left: -66px !important;
  }
  .aplayer.aplayer-fixed .aplayer-lrc {
    display: none;
  }
  .aplayer .aplayer-lrc.aplayer-lrc-hide {
      display:none !important;
  }
  .aplayer.aplayer-fixed .lrc-show {
    display: block;
    background: rgba(255, 255, 255, 0.8);
  }
</style>
<meting-js

    id="2660651585"

    server="netease"

    type="playlist"

    fixed="true"

    autoplay="false"

    loop="all"

    order="random"

    preload="auto"

    volume="0.7"

    mutex="true"

</meting-js>
<script>
  $(function(){
    $('body').on('click', '.aplayer', function(){
      if($('.aplayer-button').hasClass('aplayer-play')) {
        $('.aplayer-lrc').removeClass('lrc-show');
      } else {
        $('.aplayer-lrc').addClass('lrc-show');
      }
    })
  });
</script>
  
</body>
</html>